package com.lry.thompson;

import java.util.Set;

import static com.lry.thompson.Lexer.Token.*;

public class NfaMachine {

    private Lexer lexer;

    public NfaMachine(Lexer lexer){
        this.lexer = lexer;
        while(lexer.matchToken(EOS)){
            lexer.advance();
        }
    }

    /**
     * expr -> cat_expr OR cat_expr ......
     *
     * @param pair
     */
    public void expr(NfaPair pair) throws Exception {
        cat_expr(pair);

        while(lexer.matchToken(OR)){
            or(pair);
        }
    }

    private void or(NfaPair pair) throws Exception {
        lexer.advance();
        NfaPair curPair = new NfaPair();
        cat_expr(curPair);

        /**
         * 执行OR算法，连接pair和curPair
         * 节点1 ---a---> 节点2 OR 节点3 ---b---> 节点4
         *
         * OR算法如下：
         *
         *   ↑----ε---> 节点1 ---a---> 节点2 ---ε---↓
         *节点5                                   节点6
         *   ↓_____ε___>节点3 ---b---> 节点4----ε--↑
         */

        Nfa newStart = new Nfa();//节点5
        Nfa newEnd = new Nfa();//节点6

        //构造四根ε指针
        newStart.next = pair.start;
        newStart.next2 = curPair.start;
        pair.end.next = newEnd;
        curPair.end.next = newEnd;

        //重新把节点5，6设置为pair的头尾节点
        pair.start = newStart;
        pair.end = newEnd;
    }

    /**
     * cat_expr -> factor factor...
     *
     * @param pair
     */
    public void cat_expr(NfaPair pair) throws Exception {
        if(first_in_cat(lexer.getCurrentToken())){
            factor(pair);
        }

        /**
         * 连接运算
         * 节点1--a->节点2 连接 节点3--b->节点4
         * 节点1--a->节点2--ε-->节点3--b->节点4
         *  ε表示空
         */
        while(first_in_cat(lexer.getCurrentToken())){
            NfaPair curPair = new NfaPair();
            factor(curPair);

            //使用连接算法将pair和curPair连接起来
            pair.end.next = curPair.start;
            pair.end = curPair.end;
        }
    }

    /**
     * factor -> term | term* | term+ | term?
     *
     * @param pair
     */
    private void factor(NfaPair pair) throws Exception {
        term(pair);
        //克林闭包* ，>=0个
        if(lexer.matchToken(CLOSURE)){
            starClosure(pair);
        }
        //? ，0个或者1个
        else if(lexer.matchToken(OPTIONAL)){
            optionalClosure(pair);
        }
        //+，正闭包 >=1个
        else if(lexer.matchToken(PLUS_CLOSE)){
            plusClosure(pair);
        }
    }

    /**
     * 克林闭包 *
     * 节点1--a-->节点2
     * a*该如何表示？ ε,a,aa,aaa...
     *
     *               -------ε------
     *               ↓            ↑
     * 节点3--ε--->节点1 --a--> 节点2 ---ε-->节点4
     *  |_________________ε__________________↑
     *
     * @param pair
     */
    private void starClosure(NfaPair pair) {
        lexer.advance();

        NfaPair curPair = new NfaPair(true);
        curPair.start.next = pair.start;
        curPair.start.next2 = curPair.end;

        pair.end.next = pair.start;
        pair.end.next2 = curPair.end;

        pair.start = curPair.start;
        pair.end = curPair.end;
    }

    /**
     * ? : 0 | 1
     * 节点1--a-->节点2
     * a*该如何表示？ ε,a
     *
     * 节点3--ε--->节点1 --a--> 节点2 ---ε-->节点4
     *  |_________________ε__________________↑
     *
     * @param pair
     */
    private void optionalClosure(NfaPair pair) {
        lexer.advance();

        NfaPair curPair = new NfaPair(true);
        curPair.start.next = pair.start;
        curPair.start.next2 = curPair.end;

        pair.end.next2 = curPair.end;

        pair.start = curPair.start;
        pair.end = curPair.end;
    }

    /**
     * 正闭包 +
     * 节点1--a-->节点2
     * a*该如何表示？ a,aa,aaa...
     *
     *               -------ε------
     *               ↓            ↑
     * 节点3--ε--->节点1 --a--> 节点2 ---ε-->节点4
     *
     * @param pair
     */
    private void plusClosure(NfaPair pair) {
        lexer.advance();

        NfaPair curPair = new NfaPair(true);
        curPair.start.next = pair.start;

        pair.end.next = pair.start;
        pair.end.next2 = curPair.end;

        pair.start = curPair.start;
        pair.end = curPair.end;
    }


    private boolean first_in_cat(Lexer.Token tok) throws Exception {
        switch (tok) {
            //正确的表达式不会以 ) $ 开头,如果遇到EOS表示正则表达式解析完毕，那么就不应该执行该函数
            case CLOSE_PAREN:
            case AT_EOL:
            case OR:
            case EOS:
                return false;
            case CLOSURE:
            case PLUS_CLOSE:
            case OPTIONAL:
                //*, +, ? 这几个符号应该放在表达式的末尾
                ErrorHandler.parseErr(ErrorHandler.Error.E_CLOSE);
                return false;
            case CCL_END:
                //表达式不应该以]开头
                ErrorHandler.parseErr(ErrorHandler.Error.E_BRACKET);
                return false;
            case AT_BOL:
                //^必须在表达式的最开始
                ErrorHandler.parseErr(ErrorHandler.Error.E_BOL);
                return false;
        }
        return true;
    }

    /**
     * term -> 单字符 | expr | .通配符 | 字符集如a-z
     * @param pair
     */
    private void term(NfaPair pair) throws Exception {
        if(lexer.matchToken(L)){
            forSingleCharacter(pair);
        }else if(lexer.matchToken(OPEN_PAREN)){
            forExpr(pair);
        }else if(lexer.matchToken(ANY)){
            forDot(pair);
        }else if(lexer.matchToken(CCL_START)){
            forCharacterSet(pair);
        }
    }

    private void forExpr(NfaPair pair) throws Exception {
        lexer.advance();
        expr(pair);
        if(lexer.matchToken(CLOSE_PAREN)){
            lexer.advance();
        }else {
            ErrorHandler.parseErr(ErrorHandler.Error.E_PAREN);
        }
    }

    private void forDot(NfaPair pair) {
        Nfa start = new Nfa();

        pair.start = start;
        pair.start.next = pair.end = new Nfa();

        start.inputSet.add((byte) '\r');
        start.inputSet.add((byte) '\n');
        start.setComplement();//取反
        start.edge = Nfa.CCL;

        lexer.advance();
    }

    //[a-z],[^a-z]
    private void forCharacterSet(NfaPair pair) throws Exception {
        //越过[
        lexer.advance();

        boolean neg = false;//是否需要取反
        if(lexer.matchToken(AT_BOL)){
            neg = true;
            lexer.advance();
        }

        Nfa start = new Nfa();
        pair.start = start;
        pair.start.next = pair.end = new Nfa();
        start.edge = Nfa.CCL;

        calCharacterSet(start.inputSet);
        if(neg){
            start.setComplement();
        }
        if(!lexer.matchToken(CCL_END)){
            ErrorHandler.parseErr(ErrorHandler.Error.E_BADEXPR);
        }
        //越过]
        lexer.advance();
    }

    //a-z]
    private void calCharacterSet(Set<Byte> inputSet) {
        int first = 0;
        while(!lexer.matchToken(EOS)&&!lexer.matchToken(CCL_END)){
            if(!lexer.matchToken(DASH)){
                first = lexer.getLexeme();
            }else{
                //遇到-,越过他
                lexer.advance();
                for(;first<=lexer.getLexeme();first++){
                    inputSet.add((byte) first);
                }
            }
            lexer.advance();
        }
    }

    private void forSingleCharacter(NfaPair pair) {

        Nfa start = new Nfa();
        pair.start = start;
        pair.start.next =  pair.end = new Nfa();

        start.edge = lexer.getLexeme();
        lexer.advance();
    }

}
